'''
https://leetcode.cn/problems/word-search-ii/?envType=study-plan-v2&envId=top-interview-150
dfs + 回溯
'''

from typing import List
class Node():
    def __init__(self):
        self.passed = 0
        self.ended = None
        self.children = {}
class Solution:
    def addWord(self, word: str) -> None:
        cur = self.root
        for c in word:
            if c not in cur.children:
                cur.children[c] = Node()
            cur = cur.children[c]
            cur.passed += 1
        cur.ended = word
    def removeWord(self, word: str) -> None:
        cur = self.root
        for c in word:
            child = cur.children[c]
            cur.passed -= 1
            if child.passed == 0:
                del cur.children[c]
                return
            cur = child
        cur.ended = None

    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        m, n = len(board), len(board[0])
        self.root = root = Node()
        for word in words:
            self.addWord(word)

        res = []
        visted = [[False] * n for _ in range(m)]
        def dfs(father, i, j):
            if i < 0 or j < 0 or i >= m or j >= n or visted[i][j] or board[i][j] not in father.children:
                return
            visted[i][j] = True
            cur = father.children[board[i][j]]
            if cur.ended:
                res.append(cur.ended)
                self.removeWord(cur.ended)
            for ti, tj in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:
                dfs(cur, ti, tj)
            visted[i][j] = False

        for i in range(m):
            for j in range(n):
                dfs(root, i, j)
        return res

board = [["o","a","a","n"],
         ["e","t","a","e"],
         ["i","h","k","r"],
         ["i","f","l","v"]]
words = ["oath","pea","eat","rain","hklf", "hf"]
print(Solution().findWords(board, words))



